<?php
/**
 * 计算器处理程序
 * 思路：
 * 建立两个栈：数栈（存放数字）和符号栈（存放运算符）
 * 1、程序扫描表达式
 * 2、当发现这个字符时数字的时候，直接入数栈
 * 3、如果是运算符（1）如果符号栈为空，直接入符号栈
 *               （2）如果符号栈不为空，判断如果当前运算符的优先级小于等于符号栈顶的这个运算符的优先级，就计算（数栈弹出栈顶两个数，符号栈弹出栈顶的运算符），并把计算结果入数栈，直到当前符号的运算级别小于符号栈的优先级
 *               （3）如果符号栈不为空，判断如果当前运算符的优先级大于符号栈顶的运算符的优先级，就入栈
 * 4、当扫描完毕后，就一次弹出数栈和符号栈的数据，并计算，最后留在数栈的值，就是运算结果。
 */

//$exp = $_GET['exp'];
$exp = "71*2-50*3-3-67*6+80";
//定义一个数栈和符号栈
$numsStack = new MyStack();      //存数字
$operStack = new MyStack();      //存符号
$keepNum = '';     //用于拼接多位数
$index = 0;   //$index是一个扫描的标记
while(true){

    //依次取出字符
    $ch = substr($exp,$index,1);
    //判断$ch是否是一个符号
    if($operStack->isOper($ch) == true){
        //是运算符
        if($operStack->isEmpty()){   //如果栈为空
            $operStack->push($ch);
        }else{
            //判断运算符优先级
            //$chPRI = $operStack->PRI($ch);  //当前运算符的优先级
            //$stackPRI = $operStack->PRI($operStack->getTop());  //符号栈顶的符号的优先级
            while(!$operStack->isEmpty() && $operStack->PRI($ch) <= $operStack->PRI($operStack->getTop())) {
                //从数栈依次出栈两个数
                $num1 = $numsStack->pop();
                $num2 = $numsStack->pop();
                //再从符号栈取出一个运算符
                $oper = $operStack->pop();

                //计算结果
                $res = $operStack->getResult($num1, $num2, $oper);
                //把$res入数栈
                $numsStack->push($res);
                //把当前运算符入符号栈
            }
                $operStack->push($ch);
            /**
            //判断运算符优先级
            $chPRI = $operStack->PRI($ch);  //当前运算符的优先级
            $stackPRI = $operStack->PRI($operStack->getTop());  //符号栈顶的符号的优先级

            if($chPRI <= $stackPRI){
                //从数栈依次出栈两个数
                $num1 = $numsStack->pop();
                $num2 = $numsStack->pop();
                //再从符号栈取出一个运算符
                $oper = $operStack->pop();

                //计算结果
                $res = $operStack->getResult($num1,$num2,$oper);
                //把$res入数栈
                $numsStack->push($res);
                //把当前运算符入符号栈
                $operStack->push($ch);
            }else{
                $operStack->push($ch);
            }
             **/
        }
    }else{
        $keepNum .= $ch;
        //先判断是否已经到字符串最后，如果到最后了，就入栈；
        if($index == strlen($exp)-1){
            $numsStack->push($keepNum);
        }else{
            //判断一下$ch字符的下一个字符是数字还是运算符
            if($operStack->isOper(substr($exp,$index+1,1))){
                $numsStack->push($keepNum);
                $keepNum = '';
            }
        }
    }
    $index++;   //让$index指向下一个字符
    //判断是否已经扫描完毕
    if($index == strlen($exp)){
        break;
    }
}

/**
 * 4、当扫描完毕后，就一次弹出数栈和符号栈的数据，并计算，最后留在数栈的值，就是运算结果。只要符号栈不空，就一直计算
 */
while(!$operStack->isEmpty()){
    $num1 = $numsStack->pop();
    $num2 = $numsStack->pop();
    $oper = $operStack->pop();
    $res = $operStack->getResult($num1,$num2,$oper);
    $numsStack->push($res);
}
//当退出while循环后，在数栈中一定有一个数，就是最终结果
echo $exp .'=' . $numsStack->getTop();

/**自定义栈**/
class MyStack{
    private $top = -1;   //默认是-1，表示该栈是空的
    private $maxSize = 5;    //$maxSize表示栈最大容量
    private $stack = array();
    /**判断栈是否为空**/
    public function isEmpty(){
        if($this->top == -1){
            return true;
        }else{
            return false;
        }
    }
    /**判断是否是一个运算符**/
    public function isOper($ch){
        if($ch == '-' || $ch == '+' || $ch == '*' || $ch == '/'){
            return true;
        }else{
            return false;
        }
    }
    /**判断运算符优先级**/
    public function PRI($ch){
        if($ch == '*' || $ch == '/'){
            return 1;
        }else if($ch == '+' || $ch == '-'){
            return 0;
        }
    }
    /**返回栈顶的值,只是取出，不出栈**/
    public function getTop(){
        return $this->stack[$this->top];
    }

    /**
     * @param $num1 数字2
     * @param $num2 数字1
     * @param $oper 运算符
     * @return float|int  计算结果
     */
    public function getResult($num1,$num2,$oper){
        $res = 0;
        switch($oper){
            case '+' :
                $res = $num1 + $num2;
                break;
            case '-' :
                $res = $num2 - $num1;
                break;
            case '*' :
                $res = $num1 * $num2;
                break;
            case '/' :
                $res = $num2 / $num1;
                break;
        }
        return $res;
    }

    /**入栈操作**/
    public function push($val){
        //判断栈是否已经满了
        if($this->top == $this->maxSize-1){
            echo '<br/>栈满，不能添加';
            return;
        }
        $this->top++;
        $this->stack[$this->top] = $val;
    }

    /**出栈操作**/
    public function pop(){
        //判断栈是否为空
        if($this->top == -1){
            echo '<br/>栈空';
            return;
        }
        //把栈顶的值取出
        $topVal = $this->stack[$this->top];
        $this->top--;
        return $topVal;
    }

    /**显示栈的所有数据**/
    public function showStack(){
        //判断栈是否为空
        if($this->top == -1){
            echo '<br/>栈空';
            return;
        }
        echo '<br/>当前栈的情况是...';
        for($i=$this->top;$i>-1;$i--){
            echo '<br/>stack['.$i.']=' . $this->stack[$i];
        }
    }

}
